package com.datastructure.linkedlist;

/**
 * @author: 临晖
 * @date: 2023/10/11
 * @description:
 */


/**
 * 反转李彪
 */
public class Solution03 {
    public ListNode reverseList(ListNode head) {
        //思路一：双指针应用
        //ListNode pre = null;
        //ListNode curr = head;
        //while (curr != null) {
        //    ListNode node = curr;
        //    curr = curr.next;
        //    node.next = pre;
        //    pre = node;
        //}
        //return pre;


        //思路二：递归
        //return reverse(head, null);


        //思路三：头插法
        ListNode newHead = new ListNode(0, null);
        while (head != null) {
            ListNode node = head.next;
            head.next = newHead.next;
            newHead.next = head;
            // 头插法
            head = node;

        }

        return newHead.next;
    }

    public ListNode reverse(ListNode curr, ListNode pre) {
        if (curr == null) {
            return pre;
        }

        ListNode node = curr.next;
        curr.next = pre;
        //pre = curr;
        //curr = node;
        return reverse(node, curr);
    }
}



